/**
 *  @author dingyue.zhf
 *  @description 全排列
 */

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  /** 不断往ret里面添加新值 */
  let ret = [];
  const visited = {};
  // 如何判断重复是个问题
  /** 回溯法 */
  const backtrack = (list, i) => {
    if (i === nums.length) {
      ret.push([...list]);
      return;
    }
    for (let j = 0; j < nums.length; j++) {
      // visited[j - 1] 表示上一个节点未被访问
      // 当前节点和上一个节点相同，上个节点已经入栈可以继续追加，如果上一个节点已经访问，就不需要重复访问相同的元素了
      if (visited[j] || (nums[j] === nums[j - 1] && !visited[j - 1])) {
        continue;
      }
      const value = nums[j];
      // 递归树很重要
      list.push(value);
      visited[j] = true;
      backtrack(list, i + 1);
      visited[j] = false;
      list.pop();
    }
  };
  nums.sort();
  backtrack([], 0);
  return ret;
};
